package leetCode.q200;

import java.util.LinkedList;
import java.util.Queue;

public class BFS {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;
        int total = 0;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // 对每个点的每个方向尝试走一步
                if (grid[i][j] == '1') {
                    total++;
                    grid[i][j] = '0';
                    Queue<Integer> neighbors = new LinkedList<>();
                    // 行优先存储，把根节点的下标传入队列
                    neighbors.add(i * n + j);

                    while (!neighbors.isEmpty()) {
                        int id = neighbors.remove();
                        int row = id / n;
                        int col = id % n;
                        if (row - 1 >= 0 && grid[row-1][col] == '1') {
                            neighbors.add((row-1) * n + col);
                            grid[row-1][col] = '0';
                        }
                        if (row + 1 < m && grid[row+1][col] == '1') {
                            neighbors.add((row+1) * n + col);
                            grid[row+1][col] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col-1] == '1') {
                            neighbors.add(row * n + col-1);
                            grid[row][col-1] = '0';
                        }
                        if (col + 1 < n && grid[row][col+1] == '1') {
                            neighbors.add(row * n + col+1);
                            grid[row][col+1] = '0';
                        }
                    }
                }
            }
        }

        return total;
    }
}
